package day4;

/**
 * 
 * 问题描述：
 * 荷兰国旗问题 给定一个数组arr，和一个数num，
 * 请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 * 
 * 解题思路：
 * 利用一个指针记录所在位置，比较当前数，根据情况进行分类：
 * 当前数大于比较的数，该数不动，指针向前移动，遇到小于等于
 * 分类标准数的时候，与左侧区域后一个数交换，左侧区域右扩
 * ，指针向右移动。
 * 
 */
public class FlagOfTheNetherlands {
    
    public static void solveProblem(int[] array,int flag){
        if(array==null||array.length<2){
            return;
        }

        int index=0;
        int leftIndex=0;

        while(index<array.length){
            if(array[index]<flag){
                swap(array,leftIndex,index);
                index++;
                leftIndex++;
            }else{
                index++;
            }
        }
        
    }

    private static void swap(int[] array, int leftIndex, int i) {
        // array[leftIndex]=array[leftIndex]^array[i];
        // array[i]=array[leftIndex]^array[i];
        // array[leftIndex]=array[leftIndex]^array[i];
        //由于存在自己和自己进行了异或运算会变成零，故此处不能使用这种方式
        int temp=array[leftIndex];
        array[leftIndex]=array[i];
        array[i]=temp;
    }

    public static void main(String[] args){
        int[]  test=new int[]{4,6,8,3,4,9,7,6,0};
        solveProblem(test,5);
        for(int i=0;i<test.length;i++){
            System.out.println(test[i]);
        }
    }
}
